//给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。 
//
// 每个人都可能不喜欢其他人，那么他们不应该属于同一组。 
//
// 形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。 
//
// 当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
//输出：true
//解释：group1 [1,4], group2 [2,3]
// 
//
// 示例 2： 
//
// 
//输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= N <= 2000 
// 0 <= dislikes.length <= 10000 
// dislikes[i].length == 2 
// 1 <= dislikes[i][j] <= N 
// dislikes[i][0] < dislikes[i][1] 
// 对于 dislikes[i] == dislikes[j] 不存在 i != j 
// 
// Related Topics 深度优先搜索 图 
// 👍 89 👎 0
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;
public:
    UnionFind(int _n) : n (_n),setCount(_n),parent(_n),size(_n,1){
        //iota(parent.begin(),parent.end(),0);
        for (int i = 0; i < _n; ++i) {
            parent[i] = i;
        }
    }

    int findSet(int x){
        return parent[x] == x ? x : findSet(parent[x]);
    }

    bool uniteSet(int x ,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);
        if (x0 == y0){
            return false;
        }
        if (size[x0] < size[y0]){
            swap(x0,y0);
        }
        parent[y0] = x0;
        size[x0] += size[y0];
        --setCount;
        return true;
    }

    bool connected(int x,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);

        return x0 == y0;
    }

};


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {



        UnionFind uf(2 * N + 1);
        int x , y , nx , ny;
        for (const auto& dis : dislikes){
            x = dis[0];
            y = dis[1];

            nx = x + N;//x的另外一种颜色
            ny = y + N;//y的另外一种颜色

            if (uf.findSet(x) == uf.findSet(y))
                return false;
            uf.uniteSet(x,ny);//x跟y互斥，那么x跟y的反是一样的颜色
            uf.uniteSet(y,nx);//同上
        }

        return true;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
